package leetcode.year2021.month11;

// 416. 分割等和子集  todo 真他吗难
public class _14_1CanPartition416 {
  // 思路，首先累加所有的元素，如果不为偶数，则返回false，如果为偶数，则除以2，再求和为 sum/2的子数组是否存在(背包问题)
  public boolean canPartition(int[] nums) {
    if (nums.length < 2){
      return false;
    }
    int n = nums.length;
    int sum = 0, maxNum = 0;
    for (int i = 0; i < n; i++) {
      sum += nums[i];
      maxNum = Math.max(maxNum,nums[i]);
    }

    if (sum % 2 == 1 || maxNum > sum/2){
      return false;
    }

    int target = sum/2;

    boolean[][] dp = new boolean[n][target + 1];

    // 初始条件有，dp[i][j]表示从sum[ 0... i]的数是否存在和为 j的组合
    // 那么  dp[i][0] 都为 true，不选则为0 ，那么就是true

    for (int i = 0; i < n; i++) {
      dp[i][0] = true;
    }

    // 对于dp[0][num[i]],因为没有选取元素，所以都为false，默认都为false，不需处理

    // 寻找动态转移方程，要求取dp[i][j]的值，则分两种情况
    // 如果选取当前num[i] 大于 j， 那么当前num[i] 不可能为结果集中的值，那么可以可以得到  dp[i][j] = dp[i-1][j]。
    // 如果当前num[i] 不大于j，那么当前num[i]可能为结果集中的值，再分两种情况，选取和不选取
    //       不选取，dp[i][j] = dp[i-1][j]    选取，dp[i][j] = dp[i-1][j-nums[i]], 任意满足条件则为true
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < target+1; j++) {
        if (nums[i] > target){
          dp[i][j] = dp[i-1][j];
        } else {
          dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
        }
      }
    }

    return dp[n-1][target];
  }

  /**
   * 416. 分割等和子集
   * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [1,5,11,5]
   * 输出：true
   * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
   * 示例 2：
   *
   * 输入：nums = [1,2,3,5]
   * 输出：false
   * 解释：数组不能分割成两个元素和相等的子集。
   *
   *
   * 提示：
   *
   * 1 <= nums.length <= 200
   * 1 <= nums[i] <= 100
   */
}
